package sort

/*
	平均时间复杂度：O(nlogn)
	最好情况：O(nlogn)
	最坏情况：O(nlogn)
	空间复杂度：O(1) 需要一个栈的空间来递归
	排序方式：Inplace
	稳定性：不稳定
*/
func HeapSort(nums []int) {
	// 非叶子节点个数= lenght/2 向下取整
	for i := len(nums) / 2; i >= 0; i-- {
		adjustHeap(nums, i, len(nums))
	}

	for j := len(nums) - 1; j > 0; j-- {
		nums[0], nums[j] = nums[j], nums[0]
		adjustHeap(nums, 0, j)
	}
}

// 调整非叶子节点
func adjustHeap(nums []int, i int, length int) {
	temp := nums[i]

	for k := i*2 + 1; k < length; k = k*2 + 1 {
		if k+1 < length && nums[k+1] > nums[k] {
			k++
		}

		if nums[k] > temp {
			nums[i] = nums[k]
			i = k
		} else {
			break // 因为是自下而上的调整，所以子树已经是调整好的，如果没问题就可以break
		}
	}

	nums[i] = temp
}
